package cn.nju.sirx.algorithm.sort;

/**
 * Binary insertion sort.
 * 
 * @author SirX
 */
public class BinaryInsertionSort implements ISort {

    @Override
    public <T extends Comparable<? super T>> void sort(T[] data) {
        for (int i = 1; i < data.length; i++) {
            // binary search insertion position
            int p = 0, q = i - 1, insertPosition = 0;
            while (p <= q) {
                int mid = (p + q) / 2;
                if (data[i].compareTo(data[mid]) < 0) {
                    q = mid - 1;
                } else if (data[i].compareTo(data[mid]) > 0) {
                    p = mid + 1;
                } else {
                    insertPosition = mid + 1;
                    break;
                }
            }
            if (p > q) {
                insertPosition = p;
            }
            // move
            T tmp = data[i];
            for (int j = i; j > insertPosition;) {
                data[j] = data[--j];
            }
            data[insertPosition] = tmp;
        }
    }

}
